/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package huffman;

/**
 *
 * @author Ero
 */
import java.util.*;
import java.util.List;
public class Driver {
    
    /**
     * @param args the command line arguments
     */
    
    public static void main(String args[])
    {
    // read System.in one character at a time
    Scanner s = new Scanner(System.in).useDelimiter("");
     SinglyLinkedList<Node> freq = new SinglyLinkedList<Node>();
    // read data from input
    while (s.hasNext())
    {
    // s.next() returns string; we're interested in first char
    char c = s.next().charAt(0);
    // look up character in frequency list
    Node query = new Node(c);
    Node item = freq.remove(query);
    if (item == null)
    { // not found, add new Node
    freq.addFirst(query);
    } else { // found, increment Node
    item.frequency++;
    freq.addFirst(item);
    }
    }
    // insert each character into a Huffman tree
    PriorityQueue<HuffmanTree> trees = new PriorityVector<HuffmanTree>();    
    // merge trees in pairs until one remains
    while (trees.size() > 1)
    {
    // grab two smallest values
    HuffmanTree smallest = (HuffmanTree)trees.remove();
    HuffmanTree small = (HuffmanTree)trees.remove();
    // add bigger tree containing both
    trees.add(new HuffmanTree(smallest,small));
    }
    HuffmanTree encoding = trees.remove();
    encoding.print();
    }
    
}
